(1) Field of the Invention
This invention relates to decorrelation of signals; more particularly it relates to decorrelation of signals that have undergone convolutive mixing, and to a method, an apparatus and a computer program for implementing decorrelation.
(2) Description of the Art
Decorrelation is known: it is a form of signal processing implemented by software running on a computer system and accepting data from sensors after conversion from analogue to digital form. Two assumptions are normally made in decorrelation, stationarity and linearity, and these assumptions are also made in connection with the present invention. Stationarity means that signals and channels in which they mix do not change over a time interval during which mixed signals are sampled. Linearity means that mixtures of signals received by sensors are linear combinations of these signals. More complicated combinations featuring signal products and squares and higher order powers of signals are not considered.
The aim of decorrelation is to remove similarities between input signals, thereby eliminating redundancies. In some circumstances this may lead to recovering the signals as they were prior to mixing, but more usually it is used as a pre-processing step in an unmixing algorithm, or as part of another algorithm such as a data compression algorithm. A common usage is to separate the signals which carry meaningful data from those that arise due entirely to noise in the environment and in a receiver system which detects the signals: such separation may be an end in itself, or it may be used as part of a data compression scheme.
Decorrelation is a process of removing correlations or similarities between signal pairs in a set of signals: correlation of a pair of signals is itself defined mathematically as an integral of the signal pair's product over time. It is important that as little information as possible (preferably none) is destroyed in decorrelation process, as would occur for example if decorrelation led to one of the signals being zeroed. Use of energy preserving transforms for decorrelation avoids information being destroyed and leads to output signals with other useful properties.
If an energy preserving transform is used, it is usually required to recover decorrelated signals in decreasing order of power. This allows data compression techniques and signal/noise subspace separation techniques to be implemented very simply.
Algorithms for decorrelating signals that have been instantaneously mixed are known: they may use either transforms that are energy preserving or those that are not.
Unfortunately, an algorithm which is adequate for decorrelating signals that have been instantaneously mixed cannot cope with more difficult problems. These more difficult problems occur when an output signal from a sensor must be expressed mathematically as a convolution, i.e. a combination of a series of replicas of a signal relatively delayed with respect to one another. It is therefore referred to as the “convolutive mixing” problem.
The approach used in instantaneous algorithms has been extended to the convolutive mixing situation: from this approach it has been inferred that convolutively mixed signals can be decorrelated by the use of an energy preserving technique. This algorithm would accommodate time delays involved in mixing and decorrelation. The criterion to be imposed has however changed: i.e. pointwise decorrelation (as defined later) is no longer sufficient, instead a wider condition involving decorrelation with time delays should be imposed. This will be referred to as wide sense decorrelation, and imposing this property as imposing strong decorrelation.
Instead of the unitary matrix employed in instantaneous algorithms, an algorithm for imposing strong decorrelation by an energy preserving filter employs a paraunitary matrix. As will be described later in more detail, a paraunitary matrix is one which gives the identity matrix when multiplied by its paraconjugate matrix—a polynomial equivalent of a Hermitian conjugate matrix. A possible approach for the strong decorrelation problem is therefore to search for a paraunitary matrix that maximises a measure of the wide sense decorrelation.
In this case, it may be possible to improve on the mere return of signals in decreasing order of power. It may be possible to provide for return of signals in decreasing order of power at each frequency in a set of frequencies. Thus a first signal has more power than other signals at all frequencies and a second signal has more power than all other signals apart from the first at all frequencies etc. This property is called spectral majorisation. Spectral majorisation is useful if the algorithm is to be used for data compression or for separating signal and noise subspaces.
In “Theory of Optimal Orthonormal Filter Banks” ICASSP 1996, P. P. Vaidyanathan discloses a use for filtering techniques where both strong decorrelation and spectral majorisation are necessary, neither being sufficient without the other.
The simplest prior art method of imposing strong decorrelation involves using a multichannel whitening lattice filter. See for example S. Haykin, “Adaptive Filter Theory”, Prentice Hall, 1991, although there are many references for these techniques, based on slightly different algorithms designed with different convergence and stability properties in mind. These techniques were not designed to impose strong decorrelation directly: instead they aim to recover an innovations sequence of the mixed signals. The components of the innovations sequence so produced are strongly decorrelated as a consequence of what they are. However these techniques are not energy preserving, and so are not suitable for use in many scenarios.
In “Principal Component Filter Banks for Optimal Multiresolution Analysis”, IEEE transactions on Signal Processing Vol 43 August, 1995, M. K. Tsatsanis and G. B. Giannakis discuss how to find an optimal energy preserving and spectral majorising filter. This reference uses a frequency domain technique to show how an optimal filter can be found if infinite information is held about the signals and no constraint is placed upon the order of the filter. However it does not show either how this can be transferred to a data dependent algorithm, or how the filter can be constrained to a sensible order without losing optimality. However its calculations provide absolute performance bounds, and formed the basis of several of algorithms discussed below.
In “Multirate Systems and Filter Banks”, Prentice Hall: Signal Processing Series, 1993, P. P. Vaidyanathan discloses parameterisation of paraunitary matrices in a stage-by-stage decomposition of a paraunitary matrix in z−1: here z−1 is an operator implementing a delay. Vaidyanathan shows that a product matrix built up from a series of pairs of paraunitary matrix blocks is paraunitary: here, in a pair of blocks, one block represents a delay and the other a 2 by 2 unitary matrix implementing a Givens rotation (see U.S. Pat. No. 4,727,503). Vaidyanathan also shows that a para unitary matrix of degree N, defined later, is a product of N+1 rotations and N one-channel delay operators all implementing the same unit delay.
In “Attainable Error Bounds in Multirate Adaptive Lossless FIR Filters”, ICASSP 1995, P. A. Regalia and D Huang propose two different eigenvalue-based algorithms for strong decorrelation. Their algorithms are recursive, limited to two input signals and based upon a fixed degree lossless filter with parameters disclosed by Vaidyanathan. It is also necessary to access data from various points internal to the Vaidyanathan decomposition for use in adjusting the parameters: this adds an extra layer of processing complexity.
In “Rational Subspace Estimation using Adaptive Lossless Filter” IEEE transactions on Signal Processing Vol 40 October, 1992 P. A. Regalia and P. Loubatton disclose a different algorithm for attempting to impose both strong decorrelation and spectral majorisation. This algorithm is applicable to more than two signals, but it is based upon a deflationary approach where an optimal single signal output is first calculated, and then augmented with other outputs until one of the latter becomes insignificant. Again a fixed degree and fixed order lossless filter is parameterised as disclosed by Vaidyanathan, and the parameters are adjusted according to a stochastic algorithm, which requires information on the data flow inside the Vaidyanathan decomposition.
A different algorithm is proposed in “Design of Signal-Adapted FIR Paraunitary Filter Banks” ICASSP 1996 by P. Moulin, M. Anitescu, K. O. Kortanek and F. Potra. This uses a slightly different version of the Vaidyanathan parameterisation with a fixed degree. From the effects of a parameterised filter on one single output channel, this algorithm shows how to convert a problem of maximising power in one channel into a linear semi-infinite programming problem, which has known methods for solution. In effect the algorithm has an objective of achieving both strong decorrelation and spectral majorisation; it has a cost function which is very similar to a known N10 cost function to be described in more detail later. However it forces the paraunitary filter to be of a fixed degree, and relies upon a link between parameters and cost function being computationally tractable. For different cost functions this would not be the case.
Gradient descent methods are known which aim to adjust all parameters of a paraunitary matrix or an unmixing filter simultaneously: these methods have another difficulty, i.e. they have parameters linked to any useful measure of independence in a very complex way which does not factorise easily. This means adjusting all parameters at once: it leads to very slow algorithm convergence, which is why none of the algorithms previously mentioned use gradient descent. Gradient descent tends to be avoided in the prior art due to problems with speed and accuracy of convergence.